---
id: 5900f54c1000cf542c51005e
title: 'Завдання 478: суміші'
challengeType: 1
forumTopicId: 302155
dashedName: problem-478-mixtures
---

# --description--

Розглянемо суміш трьох речовин: $A$, $B$ та $C$. Суміші можна описати за співвідношенням речовин $A$, $B$ та $C$, тобто $(a : b : c)$. Наприклад, суміш зі співвідношенням (2 : 3 : 5) містить 20% $A$, 30% $B$ та 50% $C$.

У цьому завданні ми не можемо розділити суміш на окремі компоненти. Однак ми можемо поєднати різну кількість різних сумішей, щоб утворити суміші з новими співвідношеннями.

Наприклад, у нас є три суміші зі співвідношеннями (3 : 0 : 2), (3 : 6 : 11) та (3 : 3 : 4). Змішуючи 10 одиниць першої, 20 одиниць другої та 30 одиниць третьої, ми отримуємо нову суміш зі співвідношенням (6 : 5 : 9), оскільки: ($10 \times \frac{3}{5} + 20 \times \frac{3}{20} + 30 \times \frac{3}{10}$ : $10 \times \frac{0}{5} + 20 \times \frac{6}{20} + 30 \times \frac{3}{10}$ : $10 \times \frac{2}{5} + 20 \times \frac{11}{20} + 30 \times \frac{4}{10}$) = (18 : 15 : 27) = (6 : 5 : 9)

Однак з трьома однаковими сумішами неможливо утворити співвідношення (3 : 2 : 1), оскільки кількість $B$ завжди менша за кількість $C$.

Нехай $n$ буде натуральним числом. Припустимо, що для кожної трійки цілих чисел $(a, b, c)$ за умови $0 ≤ a, b, c ≤ n$ та $нсд(a, b, c) = 1$, ми маємо суміш зі співвідношенням $(a : b : c)$. Нехай $M(n)$ буде множиною таких сумішей.

Наприклад, $M(2)$ містить 19 сумішей з такими співвідношеннями:

{(0 : 0 : 1), (0 : 1 : 0), (0 : 1 : 1), (0 : 1 : 2), (0 : 2 : 1), (1 : 0 : 0), (1 : 0 : 1), (1 : 0 : 2), (1 : 1 : 0), (1 : 1 : 1), (1 : 1 : 2), (1 : 2 : 0), (1 : 2 : 1), (1 : 2 : 2), (2 : 0 : 1), (2 : 1 : 0), (2 : 1 : 1), (2 : 1 : 2), (2 : 2 : 1)}.

Нехай $E(n)$ буде кількістю підмножин $M(n)$, які можуть утворити суміш зі співвідношенням (1 : 1 : 1), тобто суміш з рівними частинами $A$, $B$ та $C$.

Можна довести, що $E(1) = 103$, $E(2) = 520\\,447$, $E(10)\bmod {11}^8 = 82\\,608\\,406$ та $E(500)\bmod {11}^8 = 13\\,801\\,403$.

Знайдіть $E(10\\,000\\,000)\bmod {11}^8$.

# --hints--

`mixtures()` має повернути `59510340`.

```js
assert.strictEqual(mixtures(), 59510340);
```

# --seed--

## --seed-contents--

```js
function mixtures() {

  return true;
}

mixtures();
```

# --solutions--

```js
// solution required
```
